package com.mzy.linear_struct.hot100.链表;

/**
 * @Author: mizy3
 * @Date: 2024/08/06/下午4:05
 * @Description:
 */
public class Pro142环形链表II {

    public ListNode detectCycle(ListNode head) {
        ListNode s = head;
        ListNode f = head;
        while (f != null && f.next != null) {
            f = f.next.next;
            s = s.next;
            if(s == f) {
                // 头结点到环的头部位置，跟当前节点到环的头部位置的距离是一样的
                while (s != head){
                    s = s.next;
                    head = head.next;
                }
                return s;
            };

        }

        return null;
    }
    public static void main(String[] args) {
        ListNode n1 = new ListNode(3, new ListNode(2, new ListNode(0, new ListNode(-4))));

        n1.next.next.next.next = n1.next;

        System.out.println(new Pro142环形链表II().detectCycle(n1).val);

    }
}































